#include <iostream>
#include <vector>
void insert(std::vector<int> & arr){
    int size_n = arr.size();
    for(int i=1;i<size_n;i++){
        int k = i-1;
        int base_num = arr[i];
        while(k>=0 && arr[k] > base_num){
            arr[k+1] = arr[k];
            k--;
        }
        arr[k+1] = base_num;
    }
}

void shell_insert(std::vector<int> & arr)
{
    int size_n = arr.size();
    for(int gap = size_n/2 ;gap>0;gap/=2){
        for(int i=gap;i<size_n;i++){
            int k = i - gap;
            int base_num = arr[i];
            while(k>=0 && arr[k] > base_num){
                arr[k+gap] = arr[k];
                k=k-gap;
            }
            arr[k+gap] = base_num;           
        }

    }
}

int main(){
    std::cout << "start" <<std::endl;
    std::vector<int> arr = {5,3,1,2,4};
    shell_insert(arr);
    for(int i =0;i<arr.size();i++){
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}